import java.util.Scanner;

public class Sort {
    private static void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void insertSort(int[] array){
        //外循环从前向后遍历数组
        for(int i = 1; i < array.length; i++){
            for(int j = i; j > 0; j--){
                if(array[j] < array[j - 1]){
                    swap(array, j, j - 1);
                }else{
                    break;
                }
            }
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length / 2;
        while(gap >= 1){
            for(int i = gap; i < array.length; i++){
                for(int j = i;  j - gap >= 0; j -= gap){
                    if(array[j] < array[j - gap]){
                        swap(array, j, j - gap);
                    }else{
                        break;
                    }
                }
            }
            gap /= 2;
        }
    }

    public static void selectSort(int[] array){
        int n = array.length;
        for(int i = 0; i < n; i++){
            int pos = i;
            for(int j = i + 1; j < n; j++){
                if(array[j] < array[pos]){
                    pos = j;
                }
            }
            swap(array, i, pos);
        }
    }


    // 堆排序

    private static void createHeap(int[] array){
        int n = array.length;
        for(int i = (n - 1 - 1) / 2; i >= 0; i--){
            shiftDown(array, i, n);
        }
    }

    private static void shiftDown(int[] array, int parent, int end){
        int child = parent * 2 + 1;
        while(child < end){
            if(child + 1 < end){
                child = array[child] >= array[child + 1] ? child : child + 1;
            }
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }

        }
    }

    public static void heapSort(int[] array){
        createHeap(array);
        int sz = array.length;
        while(sz > 0){
            swap(array, 0, sz - 1);
            sz--;
            shiftDown(array, 0, sz);
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        int n = array.length;
        for(int i = 0; i < n - 1; i++){
            int flag = 0;
            for(int j = 0; j < n - 1 - i; j++){
                if(array[j] > array[j + 1]){
                    swap(array, j, j + 1);
                    flag = 1;
                }
            }
            if(flag == 0){
                return;
            }
        }
    }

    // 快速
    public static void quickSort(int[] array){
        quick(array, 0, array.length - 1);
    }

    private static int partition(int[] array, int left, int right){
        int i = left;
        int j = right;
        int tmp = array[left];
        while(i < j){
            while(i < j && array[j] >= tmp){
                j--;
            }
            while(i < j && array[i] <= tmp){
                i++;
            }
            swap(array, i, j);
        }
        swap(array, left, i);
        return i;
    }

    private static int getMid(int[] array, int left, int right){
           int mid = left + (right - left) / 2;
           int a = array[left];
           int b = array[mid];
           int c = array[right];
           if(a < b ){
               if(a < c){
                   if(b < c){
                       return mid;
                   }else{
                       return right;
                   }
               }else{
                   return left;
               }
           }else{
                if(a > c) {
                    if (b < c) {
                        return right;
                    } else {
                        return mid;
                    }
                }else{
                    return left;
                }
           }
    }

    private static void quick(int[] array, int left, int right){
        if(right <= left){
            return;
        }

        //采用三数取中优化：
        int index = getMid(array, left, right);
        swap(array, left, index);

        int pivot = partition(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        quickSort(arr);

    }
}
